package com.github.yangyishe.p100;

import com.github.yangyishe.TreeNode;

/**
 * 100. 相同的树
 * https://leetcode.cn/problems/same-tree/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：p = [1,2,3], q = [1,2,3]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：p = [1,2], q = [1,null,2]
 * 输出：false
 * 示例 3：
 *
 *
 * 输入：p = [1,2,1], q = [1,1,2]
 * 输出：false
 *
 *
 * 提示：
 *
 * 两棵树上的节点数目都在范围 [0, 100] 内
 * -104 <= Node.val <= 104
 */
public class Problem100 {
    public static void main(String[] args) {
        Integer[] p=new Integer[]{1,2};
        Integer[] q=new Integer[]{1,null,2};

        TreeNode pn = TreeNode.getInstance(p);
        TreeNode qn=TreeNode.getInstance(q);

        Problem100 problem100 = new Problem100();
        boolean sameTree = problem100.isSameTree(pn, qn);
        System.out.println(sameTree);

    }

    /**
     * 思路:
     * 就是树的遍历. 选择前序遍历作为比较方法比较合适
     * 树的遍历, 几乎必用嵌套
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 前置保证: 判断节点是否为空
        // mid
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        if (p.val!=q.val) {
            return false;
        }

        // left
        boolean leftSame = isSameTree(p.left, q.left);
        if(!leftSame){
            return false;
        }

        // right
        boolean rightSame = isSameTree(p.right, q.right);
        return rightSame;
    }


}
